#pragma once
#include <vector>
#include <memory>
#include "GridGenerator.h"

// 属性映射用的KD树节点
struct PropertyKDNode {
    Point3D point;     // 节点坐标
    size_t index;      // 原始点的索引
    int axis;          // 分割轴
    std::shared_ptr<PropertyKDNode> left;   // 左子树
    std::shared_ptr<PropertyKDNode> right;  // 右子树
    
    PropertyKDNode(const Point3D& p, size_t idx, int ax) 
        : point(p), index(idx), axis(ax) {}
};

// 属性映射专用的KD树
class PropertyKDTree {
public:
    // 构建KD树
    void build(const std::vector<std::pair<Point3D, size_t>>& points);
    
    // 查找K个最近邻
    void findKNearest(const Point3D& query, int k,
                     std::vector<std::pair<double, size_t>>& nearest) const;

private:
    std::shared_ptr<PropertyKDNode> buildTree(const std::vector<size_t>& indices,
                                           int depth);
                                           
    void findNearestImpl(const Point3D& query,
                        const std::shared_ptr<PropertyKDNode>& node,
                        std::vector<std::pair<double, size_t>>& nearest,
                        int k) const;

    std::vector<std::pair<Point3D, size_t>> points_;  // 所有点的坐标和索引
    std::shared_ptr<PropertyKDNode> root_;  // 树的根节点
}; 